package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.TreeProblem;
import cn.pugle.oj.catalog.Unknown;

import java.util.Arrays;

/**
 * 右转90度. nxn的, 要求inplace.
 * <p>
 * 递归问题
 *
 * @author tzp
 * @since 2020/10/18
 */
public class LC48 implements TreeProblem {
    int n = 0;

    public void rotate(int[][] matrix) {
        n = matrix.length;
        rotate(matrix, matrix.length);
    }

    //每次rotate最外层的环状.
    public void rotate(int[][] matrix, int width) {
        if (width <= 1) return;
        //四组元素的swap;
        for (int i = 0; i < width - 1; i++) {
            int[] a = new int[]{(n - width) / 2, (n - width) / 2 + i};//x不变, y=x+i, 初始xy相等
            int[] b = new int[]{(n - width) / 2 + i, n - 1 - (n - width) / 2};//y不变, x=a的x+i
            int[] c = new int[]{n - 1 - (n - width) / 2, n - 1 - (n - width) / 2 - i};//x不变(且值=b的y), y=x-i, 初始xy相等
            int[] d = new int[]{n - 1 - (n - width) / 2 - i, (n - width) / 2};
            int tmp = matrix[a[0]][a[1]];
            matrix[a[0]][a[1]] = matrix[d[0]][d[1]];
            matrix[d[0]][d[1]] = matrix[c[0]][c[1]];
            matrix[c[0]][c[1]] = matrix[b[0]][b[1]];
            matrix[b[0]][b[1]] = tmp;
        }
        rotate(matrix, width - 2);
    }

    public static void main(String[] args) {
        int[][] a = {
                {1, 2, 3},
                {4, 5, 6},
                {7, 8, 9}};
        new LC48().rotate(a);
        System.out.println(Arrays.deepToString(a));
    }
}
